package com.lwx.leetcode.backtrack;



import com.sun.xml.internal.xsom.impl.scd.Iterators;

import java.util.*;

public class Offer77 {
    public static void main(String[] args) {
        Offer77 o = new Offer77();
        int n = 4;
        int k = 2;
        List<List<Integer>> ret = o.combine(n, k);
        for (int i = 0; i < ret.size(); i++) {
            System.out.println(ret.get(i));
        }

    }
    List<List<Integer>> ret;
    List<Boolean> visited;
    Integer k;
    int[] nums;
    public List<List<Integer>> combine(int n, int k) {
        this.k = k;
        this.nums = new int[n];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = i+1;
        }
        visited = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            visited.add(i,false);
        }
        ret = new ArrayList<>();
        Deque<Integer> q = new ArrayDeque<>();
        generateCombination(q,0);
        removeDuplicateList();
        return ret;
    }

    public void generateCombination(Deque<Integer> q,int index){
        if(q.size() == k){
            ret.add(new ArrayList<>(q));
            return;
        }
//        for (int i = index; i < nums.length; i++) {
//            if(!visited.get(i)){
//                q.addLast(nums[i]);
//                visited.set(i,true);
//                generateCombination(q,i+1);
//                visited.set(i,false);
//                q.removeLast();
//            }
//        }

        for (int i = 0; i < nums.length; i++) {
            if(!visited.get(i)){
                q.addLast(nums[i]);
                visited.set(i,true);
                generateCombination(q,i+1);
                visited.set(i,false);
                q.removeLast();
            }
        }
    }

    public void removeDuplicateList(){
        Iterator<List<Integer>> iterator = ret.iterator();
        while (iterator.hasNext()){
            List<Integer> ele = iterator.next();
            Iterator<List<Integer>> iterator1 = ret.iterator();
            while (iterator1.hasNext()){
                List<Integer> ele2 = iterator1.next();
                if(ele.contains(ele2)){
                    iterator1.remove();
                }
            }
        }
    }

}
